#include<iostream>
#include<unistd.h>
#include<fstream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>

using namespace std;

const int TABLE_SIZE = 11;


/* the hash function 
   input: char *name
   output: hash_key
 */
unsigned long ElfHash(const  char *name)
{
	unsigned long h =0,g;
	while(*name)
	{
		h = (h<<4) + *name++;
		if( g = h & 0xF0000000)
		  h ^= g >> 24;
		h &= ~g;
	}
	return h;
}

struct Person
{
	char tel[20];
	char name[20];
	int age;
	struct Person *next;
};

char s[100];
/* hash table */
Person *HashTable[11]; 

int main()
{
	ifstream fin;
	fin.open("Lab3test.DAT");
	
    /* initialize the header pointer */ 
	for(int i=0;i<11;i++)
	{
		HashTable[i] = new Person();
		HashTable[i]->next = NULL;
	}
	while(fin>>s)
	{
        /*Person *p; will be wrong for segmentation fault.because of if we just define the pointer p rather than allocate space for it , 
        it can not be put any data.{ p = HashTable[hash_key]->next }*/
		Person *p = new Person();
		char *tokenPtr = strtok(s,",");
		strcpy(p->tel,tokenPtr);

		tokenPtr = strtok(NULL,",");
		strcpy(p->name,tokenPtr);

		tokenPtr = strtok(NULL,",");
		p->age = atoi(tokenPtr);

		cout<<"tel : "<<p->tel<<"\tname : "<<p->name<<setiosflags(ios::right)<<setw(14)<<"\tage : "<<p->age<<endl;

        /* get the hash_key */
		unsigned int hash_key = (unsigned int)ElfHash(p->tel);
		hash_key %= TABLE_SIZE;

		cout<<"hash_key : "<<hash_key<<endl;
		
		/* insert the Person p into the hash table */
		if( HashTable[hash_key]->next == NULL )	
		{
			HashTable[hash_key]->next = p;
			p->next = NULL;
		}
		else
		{
			Person *q = HashTable[hash_key]->next;
			while(q->next != NULL)
			{
				q = q->next;
			}
			q->next = p;
			p->next = NULL;
		}

		memset(s,0,sizeof(s));
	}
	
	for(int i=0;i<TABLE_SIZE;i++)
	{
		printf("HashTable No [%d]-->\n",i);
		Person *q = HashTable[i]->next;
		while(q!=NULL)
		{
			cout<<"-->tel : "<<q->tel<<"\tname : "<<q->name<<setiosflags(ios::right)<<setw(14)<<"\tage : "<<q->age<<endl;
			q = q->next;
		}
		cout<<endl;
	}
	
	/* search the person's information by telephone number */
	while(1){
		cout<<"please input the telephone number you want to find : "<<endl;
		char *telToFind = new char[20];
		cin>>telToFind;
		unsigned int hash_key = (unsigned int)ElfHash(telToFind);
		hash_key %= TABLE_SIZE;
		Person *p ;
		p = HashTable[hash_key]->next;
		bool flag = true;
		while(p!=NULL)
		{
			if( strcmp(p->tel,telToFind)==0 )
			{
				flag = false ;
				break;
			}
			else p = p->next;
		}
		if(!flag)  
		{
			cout<<"=============================================================="<<endl;
			cout<<"The information has been found!"<<endl;
			cout<<"tel : "<<p->tel<<"\tname : "<<p->name<<setiosflags(ios::right)<<setw(14)<<"\tage : "<<p->age<<endl;
			cout<<"=============================================================="<<endl;
		}
		else
		{
			cout<<"=============================================================="<<endl;
			cout<<"The information can not be found!"<<endl;
			cout<<"=============================================================="<<endl;
		}
	}
	system("pause");
	return 0;
}
